In order to define road geometry that may be utilized for mapping and navigational purposes, probe data may be collected from a variety of probe sources. For example, probe data that identifies the location and heading of a probe source at a particular moment in time may be provided by mobile telephones, such as smart phones, global positioning systems (GPS) that are carried by vehicles and other types of navigation systems. Several different techniques may be employed in order to create road geometry from probe data in instances in which the probe data has a relatively high density and includes relatively high frequency trajectory information.
For example, K-means trajectory clustering associates the trajectories of a cluster of seed points that are spatially close to one another and that have similar headings. However, K-means trajectory clustering generally requires probe data that has low noise and a high probe frequency which results in relatively short distances between probe points in order for the trajectory shape to approximate the road geometry. Another technique is trajectory merging in which probe trajectories are traversed and matching graph edges are merged. Trajectories that do not match existing edges create new edges in the graph. Trajectory merging also requires probe data having relatively low noise and high probe frequency such that there are relatively short distances between probe points in order for the trajectory shape to approximate the road geometry.
A kernel density estimation technique may also be utilized to create road geometry by computing an approximate kernel density estimate of trajectories of probe points or edges over an area of interest. The kernel density estimation technique applies a threshold to produce a binary image of the roads followed by the use of various methods, such as thinning, to produce road centerlines from the binary image. The kernel density estimation technique also requires high density probe data.
Another technique utilizes principal curves. Principal curves describe self-consistent curves that pass through the middle of point data. The principal curves technique may detect individual road segments that require additional logic to address intersections and to create a road network graph. The principal curves technique also requires high probe point density and uniform probe point density to produce the desired results.
As the foregoing techniques illustrate, current techniques for creating road geometry from probe data generally rely on high frequency trajectory information and high density probe data. In instances in which the probe data is sparse and/or noisy, the foregoing techniques may be less successful in accurately generating the road geometry. In this regard, probe data that is noisy may exhibit positional errors, heading errors, sparseness, gaps and uneven probe density and other anomalies including overlapping global positioning system (GPS) data from adjacent roads. As a result of the noisy nature of probe data, ambiguous probe regions may exist in which overlapping probe points cannot be reliably classified as belonging to a specific road segment using probe properties such as speed, heading, height or density. For example, during the creation of the road geometry from relatively low frequency probe data, ambiguous probe regions may exist in instances in which multiple roads with similar headings overlap, such as ramps, bifurcations, frontage roads, highway exchange crossovers and adjacent roads. In these situations, the probe distributions for vehicles traveling along each of the multiple roads have similar headings and positionally overlap, thereby creating an ambiguous probe region in which it is difficult to reliably identify the road segment with which each probe is associated.
With reference to FIG. 1 and by way of example, at a point in which a ramp 10 exits from a highway 12, the road segments representative of the highway and the ramp are joined and the width of the road increases. Similarly, the width of the probe distribution for the probes having similar headings, such as the probes collected by vehicles traveling along the ramp or along the highway at the point at which the road segments are joined, increases. The change in the width of the probe distribution may be an indication that two or more road segments have merged or split, two or more road segments pass close to one another with the vehicles traveling along the road segments having similar probe headings, or two or more roads pass over or under one another with the vehicles traveling along the road segments having similar probe headings. With respect to FIG. 1, the grayscale of the probe points is representative of the heading of the probe point, such that probe points of the same grayscale have the same or similar headings while probe points having different grayscales have different headings.
At such locations, the failure to disambiguate the probe data so as to classify the probe points within the ambiguous probe region as belonging to a respective road segment or branch may cause the resulting road geometry to be inaccurate or imprecise. For example, the failure to disambiguate the probe points in an ambiguous probe region designated 14 in FIG. 1 brought about by the splitting of a ramp 10 from a highway 12 may create a road geometry in which the ramp merges with the highway too soon. Additionally, the failure to disambiguate the probe points in an ambiguous probe region in which two or more road segments pass close to one another with the probe points collected by the vehicles traveling along the road segments having similar probe headings, may cause the two or more road segments to be improperly merged. See, for example, the ambiguous probe region designated 16 in FIG. 1 created by the close positional relationship of a portion of the ramp and a nearby road 18. Further, in an instance in which two or more road segments cross over or under one another with the probe points in the ambiguous probe region being collected by vehicles traveling along the road segments with similar probe headings, the two or more crossing road segments may be improperly merged so as to create a false ramp geometry.
The probe distributions from multiple road segments within an ambiguous probe region may sometimes be disambiguated in instances in which the probe points include very high frequency trajectory information, such as probe points collected every ten seconds or less. However, the probe distributions in such ambiguous probe regions cannot generally be reliably disambiguated in instances in which the probe points provide relatively low frequency trajectory information, thereby potentially leading to the above-described problems in conjunction with the construction of road geometry.